//Reverse a linked list from position m to n.Do it in - place and in one - pass.
//For example : Given 1->2->3->4->5->nullptr, m = 2 and n = 4,
//return 1->4->3->2->5->nullptr.
//Note : Given m, n satisfy the following condition : 1  m  n  length of list.


#include<iostream>
using namespace std;

template<typename T>
struct ListNode{
	T _value;
	ListNode<T> *_next;
	ListNode(T value)
		:_value(value),
		_next(NULL)
	{}
};


template<typename T>
class Solution{
public:
	void reserve(ListNode<T> *root,int n,int m)
	{
		if (root == NULL)
		{
			return;
		}
		ListNode<T> *head = root;
		ListNode<T> *n_list = NULL;
		ListNode<T> *m_list = NULL;
		while (head != NULL)
		{
			--n; --m;
			if (n == 0)
			{
				n_list = head;
			}
			if (m == 0)
			{
				m_list = head;
			}
			head = head->_next;
		}
		swap(n_list->_value, m_list->_value);
	}
	void Display(ListNode<T> *head)
	{
		if (head == NULL)
		{
			return;
		}
		ListNode<T> *cur = head;
		while (cur!=NULL)
		{
			cout << cur->_value << "->" ;
			cur = cur->_next;
		}
		cout << "NULL" ;
	}
};


int main()
{
	ListNode<int> * head = new ListNode<int>(1);
	ListNode<int> *list1 = new ListNode<int>(2);
	ListNode<int> *list2 = new ListNode<int>(3);
	ListNode<int> *list3 = new ListNode<int>(4);
	ListNode<int> *list4 = new ListNode<int>(5);
	head->_next = list1;
	list1->_next = list2;
	list2->_next = list3;
	list3->_next = list4;
	Solution<int> s;
	s.reserve(head,2,4);
	s.Display(head);
	return 0;
}